Given a grid of dimension nxm where each cell in the grid can have values 0, 1 or 2 which has the following meaning: 0 : Empty cell 1 : Cells have fresh oranges 2 : Cells have rotten oranges We have to determine what is the minimum time required to rot all oranges. A rotten orange at index [i,j] can rot other fresh orange at indexes [i-1,j], [i+1,j], [i,j-1], [i,j+1] (up, down, left and right) in unit time. Example 1: Input: grid = {{0,1,2},{0,1,2},{2,1,1}} Output: 1 Explanation: The grid is- 0 1 2 0 1 2 2 1 1 Oranges at positions (0,2), (1,2), (2,0) will rot oranges at (0,1), (1,1), (2,2) and (2,1) in unit time. Example 2: Input: grid = {{2,2,0,1}} Output: -1 Explanation: The grid is- 2 2 0 1 Oranges at (0,0) and (0,1) can't rot orange at (0,3).
Code
int orangesRotting(vector<vector>& grid)
{
queue<pair<int,int>> q;
for(int i=0;i<grid.size();i++)
{
for(int j=0;j<grid[0].size();j++)
{
if(grid[i][j]==2)
q.push({i,j});
}
}
int time=0;
while(!q.empty())
{
int size=q.size();
for(int k=0;k<size;k++)
{
pair<int,int> p=q.front();
q.pop();
int i=p.first;
int j=p.second;
if(i+1>=0 && i+1<grid.size() && j>=0&& j<grid[0].size() && grid[i+1][j]==1)
{
grid[i+1][j]=2;
q.push({i+1,j});
}
if(i-1>=0&&i-1<grid.size()&&j>=0&&j<grid[0].size()&&grid[i-1][j]==1)
{
grid[i-1][j]=2;
q.push({i-1,j});
}
if(i>=0&&i<grid.size()&&j-1>=0&&j-1<grid[0].size()&&grid[i][j-1]==1)
{
grid[i][j-1]=2;
q.push({i,j-1});
}
if(i>=0&&i<grid.size()&&j+1>=0&&j+1<grid[0].size()&&grid[i][j+1]==1)
{
grid[i][j+1]=2;
q.push({i,j+1});
}
}
time++;
}
for(int i=0;i<grid.size();i++)
{
for(int j=0;j<grid[0].size();j++)
{
if(grid[i][j]==1)
return -1;
}
}
if(time-1>0)
return time-1;
else
return 0;
}